In the past, various scheduling schemes have been proposed based on packet fair queuing [A. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Network. PhD thesis, Massachusetts Institute of Technology, 1992; S. Golestani. A self-clocked fair queuing scheme for broadband applications. In INFOCOM'94, pages 636-646, June 1994; J. C. R. Bennett and H. Zhang. Wf.sup.2 q: Worst-case fair weighted weighted fair queuing. In INFOCOM'96, pages 120-128, March 1996; J. C. R. Bennett, D. C. Stephens, and H. Zhang. High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks. In ICNP'97, March 1997; S. Suri, G. Varghese, and G. Chandramenon. Leap Forward Fair Queuing. In INFOCOM'97, April 1997; D. Stilliadis and A. Varma. Design and Analysis of Frame-Based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks. In ACM SIGMETRICS'96, May 1996; J. L. Rexford, A. G. Greenberg, and F. G. Bonomi. Hardware-efficient Fair Queuing Architectures for High Speed Networks. In INFOCOM'96, March 1996]. These schemes typically require the maintenance of a clock and time-stamps for each session. Sessions are sorted based on their time-stamps and served out in that order. Proposed variants of this scheme primarily differ in the way they update the clock and session time-stamps. Similarly, they vary in the jitter introduced in the service, see J. C. R. Bennett and H. Zhang. Wf.sup.2 q: Worst-case fair weighted weighted fair queuing. In INFOCOM'96, pages 120-128, March 1996.
There are two major costs associated with the arbitration among sessions: the computation of the virtual time function, which is a dynamic measure of the normalized fair amount of service that should be received by each session, and the management of the priority queue to order the transmissions from different sessions, which has a complexity of O(log N), where N is the number of sessions.
J. C. R. Bennett, D. C. Stephens, and H. Zhang. High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks. In ICNP'97, March 1997, is an example of sample architectures to alleviate the above costs. In J. C. R. Bennett, D. C. Stephens, and H. Zhang. High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks. In ICNP'97, March 1997, the server is restricted to support a fixed number of rates. Sessions with the same rate are grouped together. It is demonstrated that a priority relationship can be maintained among sessions belonging to the same rate group without sorting. The problem is then reduced from one that schedules among all sessions to one that schedules among all sessions at the head of the groups. With such an implementation, the complexities for both priority management and virtual time computation grow with the number of discrete rates supported rather than number of sessions.
Earlier research and patents have demonstrated implementations of Packet Fair Queuing (PFQ) [J. C. R. Bennett and H. Zhang. Wf.sup.2 q: Worst-case fair weighted weighted fair queuing. In INFOCOM'96, pages 120-128, March 1996; J. C. R. Bennett and H. Zhang. Hierarchical Packet Fair Queuing Algorithms. In ACM SIGCOMM'96, pages 143-156, August 1996; J. L. Rexford, A. G. Greenberg, and F. G. Bonomi. Hardware-efficient Fair Queuing Architectures for High Speed Networks. In INFOCOM'96, March 1996; J. C. R. Bennett, D. C. Stephens, and H. Zhang. High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks. In ICNP'97, March 1997] to make bandwidth guarantees. As an example of prior art, an embodiment of such a PFQ scheme is shown. The scheme described below allocates bandwidth among sessions so as to meet their rates. A session is not allowed to receive bandwidth more than its requested rate.
Each session C.sub.i has a requested service rate, r.sub.i, represented in FIG. 1 as a fraction of line rate. The basic idea is that a session should be served once every 1/r.sub.i cell slot times. This interval is referred to as the session's time interval (TI.sub.i). The session which has not been served in the last TI.sub.i cell times should be served as soon as possible. For each session a Start Time (S.sub.i) is maintained to indicate earliest time when it is eligible to be scheduled. A finish time for each session, F.sub.i, is also maintained and is derived as F.sub.i =S.sub.i +TI.sub.i. Sessions are served out based on their finish times. The details of the algorithm are provided below:
Virtual time, updated every port cycle is defined as follows for a given port: EQU V(t+1)=V(t)+1, PA1 Let a session i be scheduled at time t. If the session is backlogged, a cell is served out, else the cycle is wasted. Its new start and finish times S.sub.i (t+) and F.sub.i (t+) are updated as follows: EQU S.sub.i (t+)=F.sub.i (t), and F.sub.i (t+)=S.sub.i (t+)+L/r.sub.i, PA1 When a new session i joins at time t, its start time is assigned as: EQU S.sub.i (t)=V(t) and F.sub.i (t)=S.sub.i (t)+L/r. PA1 At port slot time t, among all the active (backlogged) sessions the eligible ones are determined as those with: EQU S.sub.i (t).ltoreq.V(t). PA1 Among the eligible sessions the one with the smallest finish time, F.sub.i (t), is picked for service. PA1 After being served, if the session is no longer backlogged, it is removed from the list of active sessions arbitrating for port bandwidth. PA1 An inactive session i, becoming active (or backlogged) at time t, is put back into the scheduler arbitration process. Its new start time is assigned as follows: EQU S.sub.i (t)=max(S.sub.i (t-), V(t)) and F.sub.i (t)=S.sub.i (t)+L/r. PA1 For an uncongested port (i.e. sum total of all incoming traffic to port is less than or equal to the line rate), a backlogged session is limited to receive up to its rate limit. PA1 In case of congestion (the sum total of requested rate limits on backlogged sessions being greater than line rate), the scheme ensures each backlogged session receives a rate equal to its requested rate limit divided by the times the line rate is overbooked. PA1 The scheduler is overbooked with the rates requested by sessions C0 and C1. As time progresses, the start/finish times of these sessions increasingly lag behind the V(t). For example, at t=10,000, V(t)=10,000 is much ahead of F.sub.0 =6670 and F.sub.1 =6669. PA1 Session C2 becoming active at t=10,000 is stamped a start time of S.sub.2 =V(t)=10,000. PA1 Based on the criterion of serving the session with the minimum finish time, session C2 does not get served until sessions C0 and C1's finish times catch up with C2's finish time. It is beyond only this time that session C2 is served for the first time. This happens in the example at t=15000. Thus, C2 is not served for 5000 slot times. In general, a session may be starved for an arbitrary period of time after becoming active, depending on how far other sessions lag behind the virtual clock. PA1 1. Provisioning to meet the guaranteed bandwidth for sessions. Per-VC queuing is assumed. PA1 2. Minimizing jitter. It is well established that large jitter (high cell celay variation) in serving out cells for a VC leads to burstiness which can cause cells to be dropped in downstream equipment. To minimize such problems the scheduler should serve out cells in a smooth manner. PA1 3. Rate-limiting. In a heterogeneous networking environment, ATM switches often require to feed traffic into edge or ed-user equipment with limited buffering and bandwidth handling capabilities. Thus, heavy bursts of intermittent traffic destined to such equipment is bound to be dropped. Minimizing such losses is a problem of substantial interest. This objective can be achieved by allowing the network (or ATM switch) to feed traffic to the equipment at a rate it can handle. Bursts are buffered inside the network until they can be drained to the destination. To achieve the above objective, an ATM port scheduler should be capable of limiting traffic to a predetermined rate. PA1 4. Hierarchical rate limiting. The above rate-limiting may be performed at the level of a single session (similar to out bound shaping) or at the level of a set of sessions bound to the same destination, e.g. a lower speed downstream port like T1 or an xDSL pipe. In this document, such a group of sessions is referred to as a virtual link. Hierarchical rate limiting requires limiting the rate at the aggregate virtual link (VL) level and also at the individual sessions in the VL. PA1 5. Overbooking. At most times the incoming traffic on rate limited virtual links may be much smaller than its rate limit. Thus, reserving bandwidth for virtual links based on their rate limits can lead to vast underutilization of the port bandwidth. The solution to this problem requires a mechanism to overbook the rate limits on a port. Thus, the sum of the rate-limits on all virtual links belonging to a port may be greater than the port bandwidth (line rate). PA1 This is especially useful with bursty and intermittent traffic. In the best case, the traffic on incoming sources may arrive staggered in a manner that each session receives requested rate. Thus, overbooking allows us to take advantage of the statistical multiplexing. In the worst case, if sessions arrive simultaneously, such that aggregate traffic exceeds line rate, then the mechanism should allow for a graceful degradation in service to sessions. Such mechanism forms par of the present invention. PA1 6. Overbooking while meeting session guarantees. Degradation in service rate with overbooking may not be acceptable to some time sensitive sessions e.g. CBR, rt-VBR. Such sessions should be given higher priority in receiving service such that their service rates can always be met. The problem becomes more challenging when such sessions are part of a virtual link. For example, consider a virtual link requesting a rate limit of 10 Mbps. Let the VL consist of two sessions C0 and C1. Session C0 requesting a rate limit of 7 Mbps and C1 requesting a rate guarantee of 8 Mbps. When both sessions are active, the desired behavior is for C1 to receive its guaranteed 8 Mbps and C0 to receive less than or equal to 2 Mbps, such that aggregate is below the link rate limit of 10 Mbps. A mechanism to achieve such hierarchical rate limiting with overbooking while ensuring guarantees forms part of the apparatus proposed in this paper. PA1 Here, it is important to note that while the aggregate bandwidth received by virtual link may need to be limited to a particular rate, the guarantees at individual session level for sessions belonging to the virtual link must still be met. To ensure the above, two relationships are necessary implied among the rates in the scheduler: PA1 Sum total of session guarantees in a virtual link is less than the rate limit on the virtual link. PA1 The sum total of all guarantees on all sessions is less than line (port) rate.
There are other more complex virtual time functions proposed in literature, but most assume monotonically increasing functions, similar to the one in the above equation.
where
L is the length of a cell and r.sub.i is the session rate.
Note, that in the above scheme, a session is inserted into the scheduler during session setup. It remains there until the session is torn down. It is expected that the sum total of rates of all sessions is less than or equal to line rate (LR). One of the problems with the scheme in implementing overbooking is the following. An inactive (not backlogged) session may be scheduled, but not have cells, leading to the cycle being wasted. This is assuming the practical constraint that hardware does not have time to iterate the algorithm and determine a non-empty connection. In case of overbooking, the wasted cycle could have been used by another backlogged session. This problem can be solved by removing inactive sessions from the scheduler, such that the scheduler can only schedule among sessions which have cells. The above scheme requires the following modifications:
The maximum function in the equation above, ensures that a session is not served prior to S.sub.i (t-). If a session becomes empty after its last service and then backlogged again before its next scheduled start time, resetting its start time to virtual clock can lead to it getting more than its requested rate.
However, even with the modified implementation, there is a further problem in using it in an overbooking scenario, as discussed below. A general comment on PFQ implementation feasibility is necessary at this point. Determining the minimum finish time, among sessions, requires a minimum computation among all active sessions. Given a large number of sessions, this is not possible in a cell slot time. Earlier schemes have proposed maintaining sorted heaps of sessions based on their time-stamps to solve this problem. Similarly, a rate grouping scheme was proposed in [J. C. R. Bennett and H. Zhang. Wf.sup.2 q: Worst-case fair weighted weighted fair queuing. In INFOCOM'96, pages 120-128, March 1996]. The present invention works with any of such schemes to determine the minimum finish time among all sessions.
Earlier proposed implementations of PFQ schemes can implement rate limiting (the first bullet in the above itemization), by programming rate limits as the desired rates. However, in case of overbooking, the expected behavior from these implementations deviate significantly from desired behavior. Prior to analyzing the problems of implementing a rate limiting scheduler with overbooking capability using the earlier proposed PFQ schemes, a set of desired behavior from an ideal implementation is considered: